package com.kingwood.algorithm.zuochengyun.digui;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @Author 22025812
 * @Description: 含有嵌套的表达式求值
 * 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
 * @Date: 2024/3/11 10:26
 * @Modified By：
 * @Version 1.0
 */
public class BasicCalculator {

    public static int where;
    public static int calculate(String str) {
        where = 0;
        return f(str.toCharArray(), 0);
    }

    /**
     * 递归求值
     * @param str
     * @param i
     * @return
     */
    public static int f(char[] str, int i) {
       int cur = 0;
       ArrayList<Integer> numbers = new ArrayList<>();
       ArrayList<Character> ops = new ArrayList<>();

       while (i < str.length && str[i] != ')') {
            if (str[i] >= '0' && str[i] <= '9') {
                cur = cur * 10 + str[i++] - '0';
            } else if (str[i] != '(') {
                // 遇到了运算符 + - * /
                push(numbers, ops, cur, str[i++]);
                cur = 0;
            } else {
                // i (.....)
                // 遇到了左括号！
                cur = f(str, i + 1);
                i = where + 1;
            }
       }

       push(numbers, ops, cur, '+');
       where = i;
       return compute(numbers, ops);
    }

    public static void push(ArrayList<Integer> numbers, ArrayList<Character> ops, int cur, char op) {
        int n = numbers.size();
        if (n == 0 || ops.get(n - 1) == '+' || ops.get(n - 1) == '-') {
            numbers.add(cur);
            ops.add(op);
        } else {
            int topNumber = numbers.get(n - 1);
            char topOp = ops.get(n - 1);

            if (topOp == '*') {
                numbers.set(n-1, topNumber * cur);
            } else {
                numbers.set(n-1, topNumber / cur);
            }

            ops.set(n - 1, op);
        }
    }

    public static int compute(ArrayList<Integer> numbers, ArrayList<Character> ops) {
        int n = numbers.size();
        int ans = numbers.get(0);
        for (int i = 1; i < n; i++) {
            ans += ops.get(i - 1) == '+' ? numbers.get(i) : -numbers.get(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        int res = calculate(str);
        System.out.println(res);
    }
}
